#include <bits/stdc++.h>

using namespace std;

// 验证平衡二叉树
// 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution 
{
private:
    bool balance;

    // 一旦发现不平衡，返回什么高度已经不重要了
    int height(TreeNode* node)
    {
        if(!balance || node == nullptr) return 0;

        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        if(abs(leftHeight - rightHeight) > 1) balance = false;
        return max(leftHeight, rightHeight) + 1;
    }

public:
    bool isBalanced(TreeNode* root) 
    {
        // balance是全局变量，所有调用过程共享
		// 所以每次判断开始时，设置为true
        balance = true;
        height(root);
        return balance;
    }
};


class Solution 
{
private:
    // 返回 -1 表示该子树不是平衡二叉树
    // 返回 >= 0 表示该子树的高度
    int getHeight(TreeNode* node)
    {
        if(node == nullptr) return 0;
        int left = getHeight(node->left);
        if(left == -1) return -1; // 左子树不是平衡二叉树，直接返回
        int right = getHeight(node->right);
        if(right == -1 || abs(left - right) > 1) return -1;
        return max(left, right) + 1;
    }

public:
    bool isBalanced(TreeNode* root) 
    {
        return getHeight(root) != -1;
    }
};